package com.example.demo.leetcode;

/**
 * https://leetcode.cn/problems/coin-change/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * @author WangYX
 * @version 1.0.0
 * @date 2024/03/20 9:17
 */
public class _322_零钱兑换 {

    public static void main(String[] args) {
        int[] coins = {186, 419, 83, 408};
        int i = coinChange(coins, 6249);
        System.out.println(i);
    }

    /**
     * 方法一：结果不对
     *
     * 思路：先排序，然后用amount除以第一个小于amount的值，得到数量，然后在获取剩余的数。
     *  然后重复上面的思路，把得到的数量相加。
     *
     *  存在的问题：最优解，不一定是第一个小于amount的数量。
     *
     * @param coins
     * @param amount
     * @return
     */
    public static int coinChange(int[] coins, int amount) {
        quickSort(coins, 0, coins.length - 1);
        int j = coins.length - 1;
        while (j >= 0) {
            int firstMin = findFirstMin(coins, j, amount, 0);
            if (firstMin != -1) {
                return firstMin;
            }
            j--;
        }
        return -1;
    }

    public static int findFirstMin(int[] coins, int start, int amount, int num) {
        int index = -1;
        for (int i = start; i >= 0; i--) {
            //寻找第一个小于amount的值
            if (coins[i] <= amount) {
                index = i;
                break;
            }
        }
        if (index == -1) {
            return -1;
        }
        num += amount / coins[index];
        amount = amount % coins[index];

        if (amount == 0) {
            return num;
        }
        return findFirstMin(coins, start - 1, amount, num);
    }


    /**
     * 快速排序
     * <p>
     * 时间复杂度：O(nlog(n))
     * <p>
     * 空间复杂度：O(1)
     *
     * @param coins 数组
     * @param left  开始下标
     * @param right 结束下标
     */
    public static void quickSort(int[] coins, int left, int right) {
        if (left < right) {
            int partition = partition(coins, left, right);
            quickSort(coins, left, partition - 1);
            quickSort(coins, partition + 1, right);
        }
    }

    /**
     * 分区
     *
     * @param coins 数组
     * @param left  左边下标
     * @param right 右边下标
     * @return
     */
    public static int partition(int[] coins, int left, int right) {
        int pivot = coins[left];
        while (left < right) {
            while (left < right && coins[right] >= pivot) {
                right--;
            }
            coins[left] = coins[right];

            while (left < right && coins[left] < pivot) {
                left++;
            }
            coins[right] = coins[left];
        }
        coins[left] = pivot;
        return left;
    }


}
